#include <stdio.h>
#include <stdlib.h>

// 链式表

typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 初始化链表
Node *init() {
    Node *head = (Node *)malloc(sizeof(Node));
    head->next = NULL;
    return head;
}


// 尾插法
void append(Node *head, int data) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = data;
    p->next = NULL;
    if (head->next == NULL) {
        head->next = p;
    } else {
        Node *q = head->next;
        while (q->next!= NULL) {
            q = q->next;
        }
        q->next = p;
    }
}

// 头插法
void prepend(Node *head, int data) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = data;
    p->next = head->next;
    head->next = p;
}

// 按值查找
Node *search(Node *head, int data) {
    Node *p = head->next;
    while (p!= NULL) {
        if (p->data == data) {
            return p;
        }
        p = p->next;
    }
    return NULL;
}

// 按索引查找
Node *index(Node *head, int index) {
    Node *p = head->next;
    int i = 0;
    while (p!= NULL) {
        if (i == index) {
            return p;
        }
        p = p->next;
        i++;
    }
    return NULL;
}

// 删除节点
void remove(Node *head, Node *p) {
    if (p == head->next) {
        head->next = p->next;
        free(p);
        return;
    }
    Node *q = head->next;
    while (q->next!= p) {
        q = q->next;
    }
    q->next = p->next;
    free(p);
}

// 打印链表
void print(Node *head) {
    Node *p = head->next;         // 指向第一个节点
    while (p!= NULL) {
        printf("%d ", p->data);   // 打印节点数据
        p = p->next;              // 指向下一个节点
    }
    printf("\n");
}

// 销毁链表
void destroy(Node *head) {
    Node *p = head->next;
    while (p!= NULL) {
        Node *q = p->next;
        free(p);
        p = q;
    }
    free(head);
}

int main() {
    Node *head = init();
    append(head, 1);
    append(head, 2);
    append(head, 3);
    append(head, 4);
    prepend(head, 0);
    print(head);
    Node *p = search(head, 3);
    if (p!= NULL) {
        printf("Found %d at index %d\n", p->data, index(head, 2));
    } else {
        printf("Not found\n");
    }
    remove(head, p);
    print(head);
    destroy(head);
    return 0;
}